//
// Created by isabella on 25-6-3.
//
#include <Sort.h>

vector<int> MergeSort::sort(vector<int> arr) {
    return merge(arr, 0, arr.size() - 1);
}

vector<int> MergeSort::merge(vector<int> &nums, int low, int high) {
    if (low >= high) {
        return vector{nums[low]};
    }

    int mid = low + (high - low) / 2;
    auto leftArr = merge(nums, low, mid);
    auto rightArr = merge(nums, mid + 1, high);
    int m=leftArr.size(), n=rightArr.size();
    vector<int> result(m+n);
    int i=0,j=0,k=0;
    while(i<m && j<n) {
        if(leftArr[i]<=rightArr[j]) {
            result[k++] = leftArr[i++];
        }else {
            result[k++] = rightArr[j++];
        }
    }
    while(i<m) {
        result[k++] = leftArr[i++];
    }
    while(j<n) {
        result[k++] = rightArr[j++];
    }
    return result;
}
